МІНІСТЕРСТВО ОСВІТИ УКРАЇНИ Державний університет “Львівська політехніка” ПОТОКОВІ АЛГОРИТМИ І Н С Т Р У К Ц І Я №1 до лабораторної роботи з курсу “Дискретні моделі в САПР” для базового напрямку 6.0804 “Комп’ютерні науки” Затверджено: на засіданні кафедри “Системи автоматизованого провектування” Протокол N14 від 03.04. 1997 р. Львів - 1998 Потокові алгоритми. Інструкція до лабораторної роботи №1 з курсу “Дискретні моделі в САПР” для студентів базового напрямку 6.08.04 “Комп’ютерні науки”. /Укл. В.І.Каркульовський, С.П.Ткаченко, І.І.Чура. -Львів: ДУ ЛП, 1998р. -12с. Укладачі: В.І.Каркульовський, канд.техн.наук, доц., С.П.Ткаченко, канд.техн.наук, доц. І.І.Чура, канд.техн.наук, доц.. Відповідальний за випуск: Д.В.Федасюк, канд.техн.наук, доц. Рецензенти: Стех Ю.В. , канд.техн.наук, доц. Мотика І.І. , канд.техн.наук, доц. МЕТА РОБОТИ Метою даної лабораторної роботи є вивчення потокових алгоритмів. КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ ПОНЯТТЯ ПОТОКУ Сітка - це граф, в якому кожній дузі приписана деяка пропускна здатність. Введемо позначення: с(х,у) - пропускна здатність дуги (х,у), а(х,у) - вартість переміщення одиниці потоку по дузі (х,у), T(x,y) - час проходження потоку, k(x,y) - коефіцієнт підсилення потоку в дузі (x,y). Припустимо, що є граф, в якому деяка кількість одиниць потоку проходить від джерела до стоку і для кожної одиниці потоку відомий маршрут руху. Назвемо кількість одиниць, що проходять по дузі (х,у), потоком в даній дузі. Будемо потік в дузі(х,у) позначати через f(х,у) вочевидь 0
f(х,у)
с(х,у). Дуги графа можна віднести до трьох різних категорій: 1) дуги, в яких потік не може ні збільшуватись, ні зменшуватись (множина таких дуг позначається через - N); 2) дуги, в яких потік може збільшуватись (множина таких дуг позначається через - І); 3) дуги, в яких потік може зменшуватись (множина таких дуг позначається через - R); Наприклад, дуги, що мають нульову пропускну здатність або значну вартість проходження потоку, повинні належати множині N. Дуги, в яких потік менше пропускної здатності, повинні належати множині I. Дуги, по яких вже проходить деякий потік, повинні належати множині R. Дуги з множини I називають збільшуючими, а дуги з множини R - зменшуючими. Будь-яка дуга графа належить хоча б одній з трьох введених множин - I, R або N. Можливо, що якась дуга належить як множині I, так і множині R. Це має місце в тому випадку, коли по дузі вже протікає деякий потік, який можна збільшувати чи зменшувати. Відповідні дуги називаються проміжними. Позначимо через і(х,у) максимальну величину, на яку може бути збільшений потік в дузі (х,у). Відповідно позначимо через r(х,у) максимальну величину, на яку може бути зменшений потік в дузі (х,у). Очевидно, і(х,у) = с(х,у) - f(х,у) , а r(х,у) = f(х,у) Припустимо, що ми хочемо переслати додаткову кількість одиниць потоку з витоку в стік. Можливі декілька способів розв’язування даної задачі (якщо вона взагалі має рішення): Цей спосіб міг би бути реалізований, якщо б ми знайшли шлях Р з вершини “s” у вершину “t”, який би цілком складався із збільшуючих дуг (рис.1). Скільки в цьому випадку можна було б додатково переслати одиниць потоку з “s” в “t” по шляху Р? Оскільки і(х,у) являє собою максимально можливе збільшення потоку в дузі (х,у), то величина додаткового потоку з “s” в “t” по шляху Р буде складати: min {i(х,у)} (х,у) є Р s a b t i(s,a)=3 i(a,b)=2 i(b,t)=1 Рис.1. Ланцюг, що збільшує потік і включає лише прямі дуги. Для даних прикладу ( рис.1) по шляху Р можна переслати з “s” в “t” максимум одну додаткову одиницю потоку, оскільки: min{i(s,a), i(a,b), i(b,t)} = min{3, 2, 1}=1 2) Цей спосіб міг би бути реалізований, якщо б ми знайшли шлях Р з вершини “t” в вершину “s”, який цілком складався би із зменшуючих дуг (рис.2). При цьому можна було б зменшити потік в кожній дузі (х,у), що привело б до зменшення потоку з вершини “t” в вершину ”s”, тобто, до збільшення чистого поток...